#include <bits/stdc++.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>

using namespace std;

//string testFile = "data/1004812/test_data.txt";
//string testFile = "data/2861665_639096/test_data.txt";
//string testFile = "data/3512444_697518/test_data.txt";
string testFile = "data/19630345/test_data.txt";
//string testFile = "data/std/test_data.txt";

string resultFile = "rslt.txt";

typedef struct Node{
	int id;
	uint money;
	bool operator<(const Node &other)const{
		return id<other.id;
	}
	bool operator==(const Node &other)const{
		return id==other.id;
	}
}Node;

/*构建图需要的变量*/
int account_num = 0;
uint inputs[2*2000000];
uint accts[2*2000000];
vector<Node> G[2000000];
vector<Node> RG[2000000];
/**********************/

/*存放每个账户ID的字符串*/
char account_chars[2000000][12];
short length[2000000];
/**********************/

/*存放结果*/
char buf3[64*1024*1024], *hf3, *tf3;   // 31M //线程1通过hf3(head of buf3)从前往后写，线程2通过tf3(tail of buf3)从后往前写
char buf4[64*1024*1024], *hf4, *tf4;   // 42M
char buf5[64*1024*1024], *hf5, *tf5;   // 52M
char buf6[1024*1024*1024], *hf6, *tf6; // 1258M
char buf7[1468*1024*1024], *hf7, *tf7; // 1468M
int r3_1=0, r4_1=0, r5_1=0, r6_1=0, r7_1=0;
int r3_2=0, r4_2=0, r5_2=0, r6_2=0, r7_2=0;
/**********************/

/*线程锁*/
pthread_mutex_t g_mutex = PTHREAD_MUTEX_INITIALIZER;
/**********************/

/*线程1变量*/
int head_1;
int canReach1_1[2000000][2];
int canReach2_1[2000000][2];
Node layer_1[2000000];
vector<Node> ptp1_1[2000000];
vector<Node> ptp2_1[2000000];
bool vis_1[2000000];
int path_1[7], pay_1[7];
/**********************/

/*线程2变量*/
int head_2;
int canReach1_2[2000000][2];
int canReach2_2[2000000][2];
Node layer_2[2000000];
vector<Node> ptp1_2[2000000];
vector<Node> ptp2_2[2000000];
bool vis_2[2000000];
int path_2[7], pay_2[7];
/**********************/


uint parse_1(char** s){
	char *p = *s;
	uint val = *(p++) - '0';
	while(*p != ',') val = 10*val + *(p++) - '0';
	*s = p+1;
	return val;
}
uint parse_2(char** s){
	char *p = *s;
	uint val = *(p++) - '0';
	while(*p != '\r' && *p != '\n') val = 10*val + *(p++) - '0';
	*s = *p=='\r' ? p+2:p+1;
	return val;
}
void parse_to_char(uint a, char *dest, int &k){
	int n=0;
	do{dest[n++] = a%10+'0';}while((a/=10)>0);
	reverse(dest, dest+n);
	dest[n++]=',';
	length[k]=n;
}
void loadData_and_createGrap(){
	int fd = open(testFile.c_str(), O_RDONLY);
    int size = lseek(fd, 0, SEEK_END);
    char* p_map =(char*)mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
    close(fd);
	char *p = p_map;
	int n=0;
	uint money[2000000];
	while(*p != '\0'){
		inputs[n]=parse_1(&p);
		inputs[n+2000000]=parse_1(&p);
		money[n++]=parse_2(&p);
	}
	memcpy(accts, inputs, 4*n);
	memcpy(accts+n, inputs+2000000, 4*n);  
	sort(accts, accts+2*n);
	account_num = unique(accts, accts+2*n) - accts;
	unordered_map<uint, int> idHash;
	for(int i=0; i<account_num; ++i) idHash[accts[i]]=i;
	Node node;
	for(int i=0,a=0,b=0, m=0; i<n; ++i,++m){
		a=idHash[inputs[i+0]];
		b=idHash[inputs[i+2000000]];
		if(a==b) continue;
		G[a].push_back(Node{b,money[m]});
		RG[b].push_back(Node{a,money[m]});
	}
	for(int i=0; i<account_num; ++i){
		sort(G[i].begin(),G[i].end());
		sort(RG[i].begin(),RG[i].end());
		parse_to_char(accts[i],account_chars[i], i);
	}
	munmap(p_map, size);
}

inline bool check(const uint &x, const uint &y){
	return x<=5ll*y && y<=3ll*x;
}

/*线程1，从前往后寻环*/
void adpth3_1(){
	uint py1=pay_1[0],py3;
	int pos = canReach1_1[path_1[1]][1];
	for(Node &node:ptp1_1[pos]){
		if(!check(py1,node.money)) continue;
		py3 = (*find(G[node.id].begin(),G[node.id].end(), Node{path_1[0],0})).money;
		if(!check(node.money,py3) || !check(py3,py1)) continue;
		memcpy(hf3,account_chars[path_1[0]],length[path_1[0]]); hf3+=length[path_1[0]];
		memcpy(hf3,account_chars[path_1[1]],length[path_1[1]]); hf3+=length[path_1[1]];
		memcpy(hf3,account_chars[node.id],length[node.id]); hf3+=length[node.id];
		*(hf3-1) = '\n';
		r3_1++;
	}
}
void adpth4_1(){
	uint py1=pay_1[0],py2=pay_1[1],py4;
	int pos = canReach1_1[path_1[2]][1];
	for(Node &node:ptp1_1[pos]){
		if(!check(py2,node.money)) continue;
		int &n1=node.id;
		if(vis_1[n1]) continue;
		py4 = (*find(G[node.id].begin(),G[node.id].end(), Node{path_1[0],0})).money;
		if(!check(node.money,py4) || !check(py4,py1)) continue;
		memcpy(hf4,account_chars[path_1[0]],length[path_1[0]]); hf4+=length[path_1[0]];
		memcpy(hf4,account_chars[path_1[1]],length[path_1[1]]); hf4+=length[path_1[1]];
		memcpy(hf4,account_chars[path_1[2]],length[path_1[2]]); hf4+=length[path_1[2]];
		memcpy(hf4,account_chars[node.id],length[node.id]); hf4+=length[node.id];
		*(hf4-1) = '\n';
		r4_1++;
	}
}
void adpth5_1(){
	uint py1=pay_1[0],py2=pay_1[1],py5;
	int &pos2 = canReach2_1[path_1[2]][1];
	for(Node &node2:ptp2_1[pos2]){
		if(!check(py2,node2.money)) continue;
		int &n2=node2.id;
		if(vis_1[n2]) continue;
		int &pos1 = canReach1_1[n2][1];
		for(Node &node1:ptp1_1[pos1]){
			if(!check(node2.money,node1.money)) continue;
			int &n1=node1.id;
			if(vis_1[n1]) continue;
			py5 = (*find(G[node1.id].begin(),G[node1.id].end(), Node{path_1[0],0})).money;
			if(!check(node1.money,py5) || !check(py5,py1)) continue;
			memcpy(hf5,account_chars[path_1[0]],length[path_1[0]]); hf5+=length[path_1[0]];
		    memcpy(hf5,account_chars[path_1[1]],length[path_1[1]]); hf5+=length[path_1[1]];
		    memcpy(hf5,account_chars[path_1[2]],length[path_1[2]]); hf5+=length[path_1[2]];
		    memcpy(hf5,account_chars[node2.id],length[node2.id]); hf5+=length[node2.id];
		    memcpy(hf5,account_chars[node1.id],length[node1.id]); hf5+=length[node1.id];
			*(hf5-1) = '\n';
			r5_1++;
		}
	}
}
void adpth6_1(){
	uint py1=pay_1[0],py3=pay_1[2],py6;
	int pos2 = canReach2_1[path_1[3]][1];
	for(Node &node2:ptp2_1[pos2]){
		if(!check(py3,node2.money)) continue;
		int &n2=node2.id;
		if(vis_1[n2]) continue;
		int pos1 = canReach1_1[n2][1];
		for(Node &node1:ptp1_1[pos1]){
			if(!check(node2.money,node1.money)) continue;
			int &n1=node1.id;
			if(vis_1[n1]) continue;
			py6 = (*find(G[node1.id].begin(),G[node1.id].end(), Node{path_1[0],0})).money;
			if(!check(node1.money,py6) || !check(py6,py1)) continue;
			memcpy(hf6,account_chars[path_1[0]],length[path_1[0]]); hf6+=length[path_1[0]];
		    memcpy(hf6,account_chars[path_1[1]],length[path_1[1]]); hf6+=length[path_1[1]];
		    memcpy(hf6,account_chars[path_1[2]],length[path_1[2]]); hf6+=length[path_1[2]];
		    memcpy(hf6,account_chars[path_1[3]],length[path_1[3]]); hf6+=length[path_1[3]];
		    memcpy(hf6,account_chars[node2.id],length[node2.id]); hf6+=length[node2.id];
		    memcpy(hf6,account_chars[node1.id],length[node1.id]); hf6+=length[node1.id];
			*(hf6-1) = '\n';
			r6_1++;
		}
	}
}
void adpth7_1(){
	uint py1=pay_1[0],py4=pay_1[3],py7;
	int pos2 = canReach2_1[path_1[4]][1];
	for(Node &node2:ptp2_1[pos2]){
		if(!check(py4,node2.money)) continue;
		int &n2=node2.id;
		if(vis_1[n2]) continue;
		int pos1 = canReach1_1[n2][1];
		for(Node &node1:ptp1_1[pos1]){
			if(!check(node2.money,node1.money)) continue;
			int &n1=node1.id;
			if(vis_1[n1]) continue;
			py7 = (*find(G[node1.id].begin(),G[node1.id].end(), Node{path_1[0],0})).money;
			if(!check(node1.money,py7) || !check(py7,py1)) continue;
			memcpy(hf7,account_chars[path_1[0]],length[path_1[0]]); hf7+=length[path_1[0]];
		    memcpy(hf7,account_chars[path_1[1]],length[path_1[1]]); hf7+=length[path_1[1]];
		    memcpy(hf7,account_chars[path_1[2]],length[path_1[2]]); hf7+=length[path_1[2]];
		    memcpy(hf7,account_chars[path_1[3]],length[path_1[3]]); hf7+=length[path_1[3]];
		    memcpy(hf7,account_chars[path_1[4]],length[path_1[4]]); hf7+=length[path_1[4]];
		    memcpy(hf7,account_chars[node2.id],length[node2.id]); hf7+=length[node2.id];
		    memcpy(hf7,account_chars[node1.id],length[node1.id]); hf7+=length[node1.id];
			*(hf7-1) = '\n';
			r7_1++;
		}
	}
}
void dep4_1(int &u){
	vis_1[u] = true;
	for(Node &node:G[u]){
		if(node.id<=path_1[0] || vis_1[node.id]) continue;
		if(!check(pay_1[2],node.money)) continue;
		path_1[4]=node.id;
		pay_1[3]=node.money;
		if(canReach2_1[node.id][0]==path_1[0]){
			vis_1[node.id] = 1;
            adpth7_1();
            vis_1[node.id] = 0;
		}
	}
	vis_1[u] = 0;
}
void dep3_1(int &u){
	vis_1[u] = 1;
	for(Node &node:G[u]){
		if(node.id<=path_1[0] || vis_1[node.id]) continue;
		if(!check(pay_1[1],node.money)) continue;
		path_1[3]=node.id;
		pay_1[2] = node.money;
		if(canReach2_1[node.id][0]==path_1[0]){
			vis_1[node.id] = 1;
            adpth6_1();
            vis_1[node.id] = 0;
		}
		dep4_1(node.id);
	}
	vis_1[u] = 0;
}
void dep2_1(int &u){
	vis_1[u] = 1;
	for(Node &node:G[u]){
		if(node.id<=path_1[0] || vis_1[node.id]) continue;
		if(!check(pay_1[0],node.money)) continue;
		path_1[2] = node.id;
		pay_1[1] = node.money;
		if(canReach1_1[node.id][0]==path_1[0]) adpth4_1();
		if(canReach2_1[node.id][0]==path_1[0]){
			vis_1[node.id] = 1;
			adpth5_1();
			vis_1[node.id] = 0;
		}
		dep3_1(node.id);
	}
	vis_1[u] = 0;
}
void dep1_1(int &u){
	vis_1[u] = 1;
	for(Node &node:G[u]){
		if(node.id<=u) continue;
		path_1[1] = node.id;
		pay_1[0] = node.money;
		if(canReach1_1[node.id][0]==u) adpth3_1();
		dep2_1(node.id);
	}
	vis_1[u] = 0;
}
void solve_1(){
	auto start = chrono::steady_clock::now();
	bool flag = false;
	memset(vis_1, 0, sizeof(vis_1));
	for(int i=0; i<account_num; i++){canReach1_1[i][0]=-1;canReach2_1[i][0]=-1;}
	Node tmp;
	int headPos,layerSize,layerPos;
	while(1){
		pthread_mutex_lock(&g_mutex);
		if((head_2 - head_1) <= 1) flag=true; //判断后一个顶点是否被线2计算过
        head_1++;
        pthread_mutex_unlock(&g_mutex);
        if(flag) break;
		if(G[head_1].size()<1 || RG[head_1].size()<1) continue;
		headPos = 0;
		layerSize = 0;
		for(Node &node1:RG[head_1]){
			int &n1 = node1.id;
			if(n1<head_1) continue;
			for(Node &node2:RG[n1]){
				int &n2 = node2.id;
				if(n2 <= head_1) continue;
				if(canReach1_1[n2][0] != head_1){
					canReach1_1[n2][0] = head_1;
					canReach1_1[n2][1] = headPos;
					ptp1_1[headPos++].clear();
					layer_1[layerSize++] = node2;
				}
				ptp1_1[canReach1_1[n2][1]].push_back(Node{node1.id,node2.money});
			}
		}
		layerPos = 0;
		sort(layer_1, layer_1+layerSize);
		for(int k=0; k<layerSize; ++k){
			Node &node2 = layer_1[k];
			for(Node &node3:RG[node2.id]){
				int &n3 = node3.id;
				if(n3<=head_1) continue;
				if(canReach2_1[n3][0] != head_1){
					canReach2_1[n3][0] = head_1;
					canReach2_1[n3][1] = layerPos;
					ptp2_1[layerPos++].clear();
				}
				ptp2_1[canReach2_1[n3][1]].push_back(Node{node2.id,node3.money});
			}
		}
		path_1[0] = head_1;
		dep1_1(head_1);
	}
	auto end = chrono::steady_clock::now();
	double cost_t = chrono::duration<double,std::milli>(end-start).count()/1000;
	cout << "solve_1 -const- : " << cost_t  << "s" <<"       head_1 = "<<head_1<<endl;
}

/*线程2，从后往前寻环，并逆序存入*/
void adpth3_2(){
	uint py1=pay_2[0],py3;
	int pos = canReach1_2[path_2[1]][1];
	for(auto node=ptp1_2[pos].rbegin(); node!=ptp1_2[pos].rend(); ++node){
		if(!check(py1,(*node).money)) continue;
		py3 = (*find(G[(*node).id].begin(),G[(*node).id].end(), Node{path_2[0],0})).money;
		if(!check((*node).money,py3) || !check(py3,py1)) continue;
		tf3-=length[(*node).id]; memcpy(tf3,account_chars[(*node).id],length[(*node).id]);
		*(tf3+length[(*node).id]-1) = '\n';
		tf3-=length[path_2[1]]; memcpy(tf3,account_chars[path_2[1]],length[path_2[1]]);
		tf3-=length[path_2[0]]; memcpy(tf3,account_chars[path_2[0]],length[path_2[0]]);
		r3_2++;
	}
}
void adpth4_2(){
	uint py1=pay_2[0],py2=pay_2[1],py4;
	int pos = canReach1_2[path_2[2]][1];
	for(auto node=ptp1_2[pos].rbegin(); node!=ptp1_2[pos].rend(); ++node){
		if(!check(py2,(*node).money)) continue;
		int &n1=(*node).id;
		if(vis_2[n1]) continue;
		py4 = (*find(G[(*node).id].begin(),G[(*node).id].end(), Node{path_2[0],0})).money;
		if(!check((*node).money,py4) || !check(py4,py1)) continue;
		tf4-=length[(*node).id]; memcpy(tf4,account_chars[(*node).id],length[(*node).id]);
		*(tf4+length[(*node).id]-1) = '\n';
		tf4-=length[path_2[2]]; memcpy(tf4,account_chars[path_2[2]],length[path_2[2]]);
		tf4-=length[path_2[1]]; memcpy(tf4,account_chars[path_2[1]],length[path_2[1]]);
		tf4-=length[path_2[0]]; memcpy(tf4,account_chars[path_2[0]],length[path_2[0]]);
		r4_2++;
	}
}
void adpth5_2(){
	uint py1=pay_2[0],py2=pay_2[1],py5;
	int &pos2 = canReach2_2[path_2[2]][1];
	for(auto node2=ptp2_2[pos2].rbegin(); node2!=ptp2_2[pos2].rend(); ++node2){
		if(!check(py2,(*node2).money)) continue;
		int &n2=(*node2).id;
		if(vis_2[n2]) continue;
		int &pos1 = canReach1_2[n2][1];
		for(auto node1=ptp1_2[pos1].rbegin(); node1!=ptp1_2[pos1].rend(); ++node1){
			if(!check((*node2).money,(*node1).money)) continue;
			int &n1=(*node1).id;
			if(vis_2[n1]) continue;
			py5 = (*find(G[(*node1).id].begin(),G[(*node1).id].end(), Node{path_2[0],0})).money;
			if(!check((*node1).money,py5) || !check(py5,py1)) continue;
			tf5-=length[(*node1).id]; memcpy(tf5,account_chars[(*node1).id],length[(*node1).id]);
			*(tf5+length[(*node1).id]-1) = '\n';
			tf5-=length[(*node2).id]; memcpy(tf5,account_chars[(*node2).id],length[(*node2).id]);
			tf5-=length[path_2[2]]; memcpy(tf5,account_chars[path_2[2]],length[path_2[2]]);
			tf5-=length[path_2[1]]; memcpy(tf5,account_chars[path_2[1]],length[path_2[1]]);
			tf5-=length[path_2[0]]; memcpy(tf5,account_chars[path_2[0]],length[path_2[0]]);
			r5_2++;
		}
	}
}
void adpth6_2(){
	uint py1=pay_2[0],py3=pay_2[2],py6;
	int pos2 = canReach2_2[path_2[3]][1];
	for(auto node2=ptp2_2[pos2].rbegin(); node2!=ptp2_2[pos2].rend(); ++node2){
		if(!check(py3,(*node2).money)) continue;
		int &n2=(*node2).id;
		if(vis_2[n2]) continue;
		int pos1 = canReach1_2[n2][1];
		for(auto node1=ptp1_2[pos1].rbegin(); node1!=ptp1_2[pos1].rend(); ++node1){
			if(!check((*node2).money,(*node1).money)) continue;
			int &n1=(*node1).id;
			if(vis_2[n1]) continue;
			py6 = (*find(G[(*node1).id].begin(),G[(*node1).id].end(), Node{path_2[0],0})).money;
			if(!check((*node1).money,py6) || !check(py6,py1)) continue;
			tf6-=length[(*node1).id]; memcpy(tf6,account_chars[(*node1).id],length[(*node1).id]);
			*(tf6+length[(*node1).id]-1) = '\n';
			tf6-=length[(*node2).id]; memcpy(tf6,account_chars[(*node2).id],length[(*node2).id]);
			tf6-=length[path_2[3]]; memcpy(tf6,account_chars[path_2[3]],length[path_2[3]]);
			tf6-=length[path_2[2]]; memcpy(tf6,account_chars[path_2[2]],length[path_2[2]]);
			tf6-=length[path_2[1]]; memcpy(tf6,account_chars[path_2[1]],length[path_2[1]]);
			tf6-=length[path_2[0]]; memcpy(tf6,account_chars[path_2[0]],length[path_2[0]]);
			r6_2++;
		}
	}
}
void adpth7_2(){
	uint py1=pay_2[0],py4=pay_2[3],py7;
	int pos2 = canReach2_2[path_2[4]][1];
	for(auto node2=ptp2_2[pos2].rbegin(); node2!=ptp2_2[pos2].rend(); ++node2){
		if(!check(py4,(*node2).money)) continue;
		int &n2=(*node2).id;
		if(vis_2[n2]) continue;
		int pos1 = canReach1_2[n2][1];
		for(auto node1=ptp1_2[pos1].rbegin(); node1!=ptp1_2[pos1].rend(); ++node1){
			if(!check((*node2).money,(*node1).money)) continue;
			int &n1=(*node1).id;
			if(vis_2[n1]) continue;
			py7 = (*find(G[(*node1).id].begin(),G[(*node1).id].end(), Node{path_2[0],0})).money;
			if(!check((*node1).money,py7) || !check(py7,py1)) continue;
			tf7 -= length[(*node1).id]; memcpy(tf7,account_chars[(*node1).id],length[(*node1).id]);
			*(tf7+length[(*node1).id]-1) = '\n';
			tf7-=length[(*node2).id]; memcpy(tf7,account_chars[(*node2).id],length[(*node2).id]);
			tf7-=length[path_2[4]]; memcpy(tf7,account_chars[path_2[4]],length[path_2[3]]);
			tf7-=length[path_2[3]]; memcpy(tf7,account_chars[path_2[3]],length[path_2[3]]);
			tf7-=length[path_2[2]]; memcpy(tf7,account_chars[path_2[2]],length[path_2[2]]);
			tf7-=length[path_2[1]]; memcpy(tf7,account_chars[path_2[1]],length[path_2[1]]);
			tf7-=length[path_2[0]]; memcpy(tf7,account_chars[path_2[0]],length[path_2[0]]);
			r7_2++;
		}
	}
}
void dep4_2(int &u){
	vis_2[u] = true;
	for(auto node=G[u].rbegin(); node!=G[u].rend(); ++node){
		if((*node).id<=path_2[0] || vis_2[(*node).id]) continue;
		if(!check(pay_2[2],(*node).money)) continue;
		path_2[4]=(*node).id;
		pay_2[3]=(*node).money;
		if(canReach2_2[(*node).id][0]==path_2[0]){
			vis_2[(*node).id] = 1;
            adpth7_2();
            vis_2[(*node).id] = 0;
		}
	}
	vis_2[u] = 0;
}
void dep3_2(int &u){
	vis_2[u] = 1;
	for(auto node=G[u].rbegin(); node!=G[u].rend(); ++node){
		if((*node).id<=path_2[0] || vis_2[(*node).id]) continue;
		if(!check(pay_2[1],(*node).money)) continue;
		path_2[3]=(*node).id;
		pay_2[2] = (*node).money;
		if(canReach2_2[(*node).id][0]==path_2[0]){
			vis_2[(*node).id] = 1;
            adpth6_2();
            vis_2[(*node).id] = 0;
		}
		dep4_2((*node).id);
	}
	vis_2[u] = 0;
}
void dep2_2(int &u){
	vis_2[u] = 1;
	for(auto node=G[u].rbegin(); node!=G[u].rend(); ++node){
		if((*node).id<=path_2[0] || vis_2[(*node).id]) continue;
		if(!check(pay_2[0],(*node).money)) continue;
		path_2[2] = (*node).id;
		pay_2[1] = (*node).money;
		if(canReach1_2[(*node).id][0]==path_2[0]) adpth4_2();
		if(canReach2_2[(*node).id][0]==path_2[0]){
			vis_2[(*node).id] = 1;
			adpth5_2();
			vis_2[(*node).id] = 0;
		}
		dep3_2((*node).id);
	}
	vis_2[u] = 0;
}
void dep1_2(int &u){
	vis_2[u] = 1;
	for(auto node=G[u].rbegin(); node!=G[u].rend(); ++node){
		if((*node).id<=u) continue;
		path_2[1] = (*node).id;
		pay_2[0] = (*node).money;
		if(canReach1_2[(*node).id][0]==u) adpth3_2();
		dep2_2((*node).id);
	}
	vis_2[u] = 0;
}
void solve_2(){
	auto start = chrono::steady_clock::now();
	bool flag = false;
	memset(vis_2, 0, sizeof(vis_2));
	for(int i=0; i<account_num; i++){canReach1_2[i][0]=-1;canReach2_2[i][0]=-1;}
	Node tmp;
	int headPos,layerSize,layerPos;
	while(1){
		pthread_mutex_lock(&g_mutex);
		if((head_2 - head_1) <= 1) flag=true;  //判断前一个顶点是否被线1计算过
        head_2--;
        pthread_mutex_unlock(&g_mutex);
        if(flag) break;
		if(G[head_2].size()<1 || RG[head_2].size()<1) continue;
		headPos = 0;
		layerSize = 0;
		for(Node &node1:RG[head_2]){
			int &n1 = node1.id;
			if(n1<head_2) continue;
			for(Node &node2:RG[n1]){
				int &n2 = node2.id;
				if(n2 <= head_2) continue;
				if(canReach1_2[n2][0] != head_2){
					canReach1_2[n2][0] = head_2;
					canReach1_2[n2][1] = headPos;
					ptp1_2[headPos++].clear();
					layer_2[layerSize++] = node2;
				}
				ptp1_2[canReach1_2[n2][1]].push_back(Node{node1.id,node2.money});
			}
		}
		layerPos = 0;
		sort(layer_2, layer_2+layerSize);
		for(int k=0; k<layerSize; ++k){
			Node &node2 = layer_2[k];
			for(Node &node3:RG[node2.id]){
				int &n3 = node3.id;
				if(n3<=head_2) continue;
				if(canReach2_2[n3][0] != head_2){
					canReach2_2[n3][0] = head_2;
					canReach2_2[n3][1] = layerPos;
					ptp2_2[layerPos++].clear();
				}
				ptp2_2[canReach2_2[n3][1]].push_back(Node{node2.id,node3.money});
			}
		}
		path_2[0] = head_2;
		dep1_2(head_2);
	}
	auto end = chrono::steady_clock::now();
	double cost_t = chrono::duration<double,std::milli>(end-start).count()/1000;
	cout << "solve_2 -const- : " << cost_t  << "s" << endl;
}


void save(){
	char tmp[20];
	int m=sprintf(tmp,"%d\n",r3_1+r4_1+r5_1+r6_1+r7_1 + r3_2+r4_2+r5_2+r6_2+r7_2);
	int n=m;
	n += sizeof(buf3) - (tf3 - hf3); //存放长度为3的环所用的字节数
	n += sizeof(buf4) - (tf4 - hf4);
	n += sizeof(buf5) - (tf5 - hf5);
	n += sizeof(buf6) - (tf6 - hf6);
	n += sizeof(buf7) - (tf7 - hf7);
	
	int fd = open(resultFile.c_str(), O_RDWR|O_CREAT, 0666);
	lseek(fd, n-1, SEEK_SET);
	write(fd, "", 1);
	char* p_mmap =(char*)mmap(NULL, n, PROT_WRITE, MAP_SHARED, fd, 0);
	char* p = p_mmap;

	memcpy(p, tmp, m); p+=m; //写入找到的环的总个数
	
	int len = hf3-buf3;
	memcpy(p, buf3, len); p+=len;
	len = buf3 + sizeof(buf3) - tf3;
	memcpy(p, tf3, len); p+=len;
	
	len = hf4-buf4; 
	memcpy(p, buf4, len); p+=len;
	len = buf4 + sizeof(buf4) - tf4;
	memcpy(p, tf4, len); p+=len;
	
	len = hf5-buf5; 
	memcpy(p, buf5, len); p+=len;
	len = buf5 + sizeof(buf5) - tf5;
	memcpy(p, tf5, len); p+=len;
	
	len = hf6-buf6; 
	memcpy(p, buf6, len); p+=len;
	len = buf6 + sizeof(buf6) - tf6;
	memcpy(p, tf6, len); p+=len;
	
	len = hf7-buf7; 
	memcpy(p, buf7, len); p+=len;
	len = buf7 + sizeof(buf7) - tf7;
	memcpy(p, tf7, len); p+=len;
	
	*p = '\0';
	
	munmap(p_mmap, n);
	close(fd);
}

int main(int argc, char* argv[]){
	clock_t startTime = clock();
	loadData_and_createGrap();
	clock_t endTime = clock();
	cout << "LoadDataAndCreateGraph: " << (float)(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
	
	hf3=buf3;tf3=buf3+sizeof(buf3);
	hf4=buf4;tf4=buf4+sizeof(buf4);
	hf5=buf5;tf5=buf5+sizeof(buf5);
	hf6=buf6;tf6=buf6+sizeof(buf6);
	hf7=buf7;tf7=buf7+sizeof(buf7);
	head_1 = -1;
	head_2 =account_num;
	auto start = chrono::steady_clock::now();
	vector<thread> threadpool(2);
	threadpool[0] = thread(&solve_1);
	threadpool[1] = thread(&solve_2);
	threadpool[0].join();
	threadpool[1].join();
	auto end = chrono::steady_clock::now();
	double cost_t = chrono::duration<double,std::milli>(end-start).count()/1000;
	cout << "compute : " << cost_t  << "s" << endl;
	
	
	startTime = clock();
	save();
	endTime = clock();
	cout << "save: " << (float)(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
	
	
	cout<<endl;
	cout<<"p3_1 = "<<r3_1<<endl;
	cout<<"p4_1 = "<<r4_1<<endl;
	cout<<"p5_1 = "<<r5_1<<endl;
	cout<<"p6_1 = "<<r6_1<<endl;
	cout<<"p7_1 = "<<r7_1<<endl<<endl;
	cout<<"p3_2 = "<<r3_2<<endl;
	cout<<"p4_2 = "<<r4_2<<endl;
	cout<<"p5_2 = "<<r5_2<<endl;
	cout<<"p6_2 = "<<r6_2<<endl;
	cout<<"p7_2 = "<<r7_2<<endl<<endl;
	int all = r3_1+r4_1+r5_1+r6_1+r7_1;
	all    += r3_2+r4_2+r5_2+r6_2+r7_2;
	cout<<"all_loops = "<<all<<endl;
	exit(0);
}